package com.hspedu.newData.dmsxl.动态规划.基础;

import org.junit.Test;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-11 
 * @Version: 1.0
 */

public class LC338比特位计数 {

    public int[] countBits(int n) {

        int[] dp = new int[n+1];
        if (n == 0) return dp;

        int j = 0;
        for (int i = 1; i < n + 1;) {
            if (i == Math.pow(2,j)){
                dp[i] = 1;
                j++;
                i++;
            }else {
                int x = 1;
                int pow = (int) Math.pow(2, j-1);
                while (i<n+1 && i < Math.pow(2,j)){
                    dp[i++] = dp[pow] + dp[x++];
                }
            }
        }
        return dp;
    }


    @Test
    public void test() {
        // 测试代码

        countBits(10);
    }


}
